Nha An ninh Quân đội được thành lập cùng lúc với Bộ Tổng tham mưu của Quân đội Quốc gia vào đầu tháng 5 năm 1952. Nha này khi ấy trực thuộc Bộ Tổng tham mưu với vị Giám đốc đầu tiên là Thiếu tá Trần Văn Đôn. Tới cuối năm 1953, Trung tá Đôn được cử làm Tham mưu trưởng Bộ Tổng tham mưu. Đại tá Mai Hữu Xuân, nhân viên cao cấp của ngành Cảnh sát-Công an mang cấp bậc đồng hoá thay thế, chứng tỏ Nha này ngay khi thành lập đã được chú ý đặc biệt.

Ngành an ninh lúc ấy không có hệ thống hàng dọc, các cơ quan và đơn vị tuỳ theo sự tín nhiệm đề cử sĩ quan an ninh để hoạt động với trách nhiệm của đơn vị trưởng. Báo cáo về Nha Trung ương các tin tức về an ninh nhân sự và đơn vị. Tới cuối năm 1954, để phụ trách an ninh toàn lãnh thổ. Các Đại đội được thành lập tại các Quân khu. Mỗi Quân khu tuỳ theo tầm mức quan trọng được phép thành lập từ 2 đến 4 Đại đội và được duy trì đến giữa năm 1955 rồi giải tán.

Sau đó, ngành An ninh Quân đội được cải tổ và bắt đầu có một hệ thống hàng dọc từ trên xuống dưới. Ở Bộ Tổng tham mưu, Bộ tư lệnh Quân đoàn, Quân chủng, Sư đoàn, Không đoàn, Hải đoàn, Bộ chỉ huy Tiểu khu... có Phòng 2. Các Ban chỉ huy Lữ đoàn, Trung đoàn, Liên đoàn, Phi đoàn, Hạm đội, Tiểu đoàn, Yếu khu Thị xã và Chi khu quân sự... có Ban 2. Các Phòng, Ban này đảm trách về an ninh trong đơn vị của mình.

Đến năm 1965, Nha An ninh Quân đội được đổi tên thành Cục An ninh Quân đội, trực thuộc Tổng cục Chiến tranh Chính trị theo hệ thống điều hành của Bộ Tổng tham mưu cho đến tháng 4 năm 1975.